package org.example.algorithm.bst;

import org.example.algorithm.TreeNode;

import java.util.Stack;

public class FlattenSolution {
    private TreeNode head;

    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(1);
        treeNode.right = new TreeNode(2);
        treeNode.right.left = new TreeNode(3);
        FlattenSolution solution = new FlattenSolution();
        solution.flatten(treeNode);
    }

    //时间复杂度O(n)，空间O(1)
    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }
        TreeNode cur = root;
        while (cur != null) {
            if (cur.left != null) {
                TreeNode left = cur.left;
                TreeNode leftLast = cur.left;
                while (leftLast.right != null) {
                    leftLast = leftLast.right;
                }
                leftLast.right = cur.right;
                cur.left = null;
                cur.right = left;
            }
            cur = cur.right;
        }
    }

    //先序遍历，边遍历边修改指针
    public void flatten2(TreeNode root) {
        if (root == null) {
            return;
        }
        TreeNode pre = null;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            TreeNode left = node.left;
            TreeNode right = node.right;
            if (pre == null) {
                pre = node;
                pre.left = null;
            } else {
                pre.right = node;
                pre.left = null;
                pre = pre.right;
            }
            if (right != null) {
                stack.push(right);
            }
            if (left != null) {
                stack.push(left);
            }
        }
    }

    //头插法
    public void flatten3(TreeNode root) {
        if (root == null) {
            return;
        }
        flatten(root.right);
        flatten(root.left);
        root.right = head;
        root.left = null;
        head = root;
    }
}
